Some applications (e.g., video games, architectural rendering, etc.) involve representing three-dimensional objects to a user. In one example, an adventure game played by a user in a virtual reality environment may require the generation of virtual trees, rocks, and people. In another example, a mapping application may require the representation of buildings. In some applications, each such object can include a triangular mesh having a plurality of vertices, i.e., points in space that form triangles. Such a triangular mesh involves a plethora of data that may be stored on disk and transmitted to the user. Practical implementations of storing and transmitting the triangular mesh data representing a virtual object include simplifying the triangular mesh data by reducing the number of triangles.
A conventional approach to simplifying such triangular mesh data involves removing triangles from a triangular mesh represented by the triangle mesh data based on a mesh error metric between the original triangle mesh data and the simplified mesh data. For example, one such approach may take the form of an evaluation of a mesh error metric after a deletion of each vertex of the triangle mesh. Accordingly, at each step, a number of triangles having a common vertex are replaced with one of a number of new configurations of a smaller number of triangles after that common vertex is removed, such that the mesh error metric is minimized. Multiple steps of removing such vertices may result in the reduction of the number of triangles until a specified number of triangles is achieved.